#include <algorithm>
#include "complexObj.h"
#include "string.h"

int Compare::type = 0;

ComplexObj::ComplexObj(string file){
    pointSize = 0;
    faceSize = 0;
    materialSize = 0;
    vtSize = 0;

    FILE *fp = fopen(file.c_str(), "r");
    point.clear();
    point.push_back(Vec(0,0,1));
    vt.push_back(Vec(0,0,1));
    triangle.clear();


    char buf[256];
    int vIndices[3];
    int t[3];
    int lineNumber = 0;
    Material curMaterial = Material();
    while(fscanf(fp, "%s", buf) != EOF){
        lineNumber++;
        switch(buf[0]){
        case '#':				/* comment */
            /* eat up rest of line */
            fgets(buf, sizeof(buf), fp);
            break;
        case 'v':				/* v, vn, vt */
            switch(buf[1]){
            case '\0':			    /* vertex */{
                Vec vP;
                if(fscanf(fp, "%lf %lf %lf", &vP.x, &vP.y, &vP.z)==3){
                    point.push_back(vP);
                }
                else
                {
                    printf("Error: Wrong Number of Values(Should be 3). at Line %d\n",lineNumber);
                }
                break;
            }
            case 't':			    /* vt */{
                Vec vP;
                if(fscanf(fp, "%lf %lf", &vP.x, &vP.y) == 2){
                    vt.push_back(vP);
                }
                else
                {
                    printf("Error: Wrong Number of Values(Should be 3). at Line %d\n",lineNumber);
                }
                break;
            }
            default:
                /* eat up rest of line */
                fgets(buf, sizeof(buf), fp);
                break;
            }
            break;

        case 'f':				/* face */
        {
            int v,n;
            if(fscanf(fp, "%s", buf) != 1)
            {
                printf("Error: Wrong Face at Line %d\n", lineNumber);
            }

            /* can be one of %d, %d//%d, %d/%d, %d/%d/%d %d//%d */
            if (strstr(buf, "//"))
            {
                /* v//n */
                if( sscanf(buf, "%d//%d", &vIndices[0],&n) ==2  &&
                        fscanf(fp, "%d//%d", &vIndices[1], &n) ==2  &&
                        fscanf(fp, "%d//%d", &vIndices[2], &n) ==2)
                {
                    triangle.push_back(Triangle(vIndices[0], vIndices[1], vIndices[2], point, "triangle", curMaterial));
                    if (fscanf(fp, "%d//%d", &vIndices[1], &n) ==2){
                        triangle.push_back(Triangle(vIndices[0], vIndices[2], vIndices[1], point, "triangle", curMaterial));
                    }
                }
                else
                {
                    printf("Error: Wrong Face at Line %d\n",lineNumber);
                }

            }
            else if (sscanf(buf, "%d/%d/%d", &v, &t[0], &n) == 3)
            {
                /* v/t/n */
                vIndices[0] = v;
                if( fscanf(fp, "%d/%d/%d", &vIndices[1], &t[1], &n) ==3 &&
                        fscanf(fp, "%d/%d/%d", &vIndices[2], &t[2], &n) ==3 )
                {
                    triangle.push_back(Triangle(vIndices[0], vIndices[1], vIndices[2], point, "triangle", curMaterial, vt[t[0]], vt[t[1]], vt[t[2]]));
                    if (fscanf(fp, "%d/%d/%d", &vIndices[1], &t[1], &n) == 3){
                        triangle.push_back(Triangle(vIndices[0], vIndices[2], vIndices[1], point, "triangle", curMaterial, vt[t[0]], vt[t[2]], vt[t[1]]));
                    }
                }
                else
                {
                    printf("Error: Wrong Face at Line %d\n",lineNumber);
                }
            }
            else if (sscanf(buf, "%d/%d", &v, &t[0]) == 2)
            {
                /* v/t */
                vIndices[0] = v;
                if( fscanf(fp, "%d/%d", &vIndices[1], &t[1]) ==2 &&
                        fscanf(fp, "%d/%d", &vIndices[2], &t[2]) ==2 )
                {
                    triangle.push_back(Triangle(vIndices[0], vIndices[1], vIndices[2], point, "triangle", curMaterial, vt[t[0]], vt[t[1]], vt[t[2]]));
                    if (fscanf(fp, "%d/%d", &vIndices[1], &t[1]) ==2){
                        triangle.push_back(Triangle(vIndices[0], vIndices[2], vIndices[1], point, "triangle", curMaterial, vt[t[0]], vt[t[2]], vt[t[1]]));
                    }
                }
                else
                {
                    printf("Error: Wrong Face at Line %d\n",lineNumber);
                }
            }
            else
            {
                /* v */
                if( sscanf(buf, "%d", &vIndices[0]) ==1 &&
                        fscanf(fp, "%d", &vIndices[1])  ==1 &&
                        fscanf(fp, "%d", &vIndices[2])  ==1 )
                {
                    triangle.push_back(Triangle(vIndices[0], vIndices[1], vIndices[2], point, "triangle", curMaterial));
                    if (fscanf(fp, "%d", &vIndices[1]) ==1){
                        triangle.push_back(Triangle(vIndices[0], vIndices[2], vIndices[1], point, "triangle", curMaterial));
                    }
                }
                else
                {
                    printf("Error: Wrong Face at Line %d\n",lineNumber);
                }
            }
            break;
        }
        case 'm':{
            if (strcmp(buf, "mtllib") == 0){
                cout << "ok" << endl;
                fscanf(fp, "%s", buf);
                cout << buf << endl;
                readMtlFile(buf);
            }
            fgets(buf, sizeof(buf), fp);
            break;
        }

        case 'u':{
            if (strcmp(buf, "usemtl") == 0){
                fscanf(fp, "%s", buf);
                curMaterial = materials[MTL[buf]];
            }
            fgets(buf, sizeof(buf), fp);
            break;
        }


        default:
            /* eat up rest of line */
            int t,n;
            if (sscanf(buf, "%d/%d/%d", &vIndices[1], &t, &n) == 3){
                triangle.push_back(Triangle(vIndices[0], vIndices[2], vIndices[1], point, "triangle", curMaterial));
            }
            fgets(buf, sizeof(buf), fp);
            break;
        }
    }
    fclose(fp);
    faceSize = triangle.size();
    pointSize = point.size() - 1;
    vtSize = vt.size() - 1;
    cout << "faceSize : " << faceSize << endl;
    cout << "pointSize : " << pointSize << endl;
    //root = new Node();
    //makeKDTree(root);

}

void ComplexObj::readMtlFile(string file)
{
    FILE* fp = fopen(file.c_str(), "r");
    int lineNumber = 0;
    char buf[256];
    Material* cur = 0;
    if(fp != 0){
        while (fscanf(fp, "%s", buf) != EOF){
            lineNumber++;
            switch (buf[0]){
            case 'n':{
                if (strcmp(buf, "newmtl") == 0){
                    fscanf(fp, "%s", buf);
                    MTL[string(buf)] = materialSize;
                    materials.push_back(Material());
                    cur = &materials[materialSize];
                    materialSize++;
                    if (strcmp(buf, "box") == 0){
                        cur->reflect = 0.7;
                        cur->diffuse = 0.1;
                        cout << "getbox" << endl;
                    }
                    if (strcmp(buf, "dragon") == 0){
                        cur->reflect = 0.5;
                        cur->diffuse = 0.5;
                        cout << "getdragon" << endl;
                    }
                }else {
                    printf("Error: Wrong at Line %d\n",lineNumber);
                }
                break;
            }
            case 'K':{
                if (buf[1] == 'd'){
                    fscanf(fp, "%lf %lf %lf", &cur->color.r, &cur->color.g, &cur->color.b);
                }else{
                    fgets(buf, sizeof(buf), fp);
                }
                break;
            }
            case 'm':{
                if (strcmp(buf, "map_Kd") == 0){
                    char file[256];
                    memset(file, 0, sizeof(file) );
                    fgets(buf, sizeof(buf), fp);
                    if (sscanf(buf, "%s", file) == 1){
                        cout << file << endl;
                        if (cur == 0){
                            printf("error! mtl file wrong!\n");
                        }else
                        cur->setTexture(file);
                    }
                }else{
                    fgets(buf, sizeof(buf), fp);
                }
                break;
            }
            default:{
                fgets(buf, sizeof(buf), fp);
                break;
            }
            }
        }
    }else {
        cout << "error the mtl file is missing!" << endl;
    }
}
ComplexObj::~ComplexObj()
{
    delete []neighborHead;
    delete []neighborSet;
    delete []neiFace;
    delete []line;
    delete heap;
    delete []father;
    delete []pointKey;
}

void ComplexObj::makeKDTree(Node *cur)
{
    for (int i = 0 ; i < faceSize; i++){
        cur->face.push_back(&triangle[i]);
        cur->faceSize++;
        cur->cube.update(&triangle[i]);
    }
    for (int i = 0; i < pointSize; i++){
        cur->point.push_back(&point[i]);
        cur->PointSize++;
    }
    cout << "make start" << endl;
    cur->makeKDTree(0);
    cout << "make complete" << endl;
}

void ComplexObj::inse(int x, int y)
{
    if (x > y) return;
    line[lineSize].x = x;
    line[lineSize].y = y;
    lineSize++;

    usedSize++;
    neighborSet[usedSize].line = &line[lineSize - 1];
    neighborSet[usedSize].next = neighborHead[x];
    neighborHead[x] = usedSize;

    usedSize++;
    neighborSet[usedSize].line = &line[lineSize - 1];
    neighborSet[usedSize].next = neighborHead[y];
    neighborHead[y] = usedSize;



}

void ComplexObj::inn(int x, Triangle *tt)
{
    listSize++;
    neiFace[listSize].face = tt;
    neiFace[listSize].next = start[x];
    start[x] = listSize;
}

void ComplexObj::updateP(const int& x, const int& updateKey)
{
    for (int k = neighborHead[x]; k != 0 ; k = neighborSet[k].next){
        if (neighborSet[k].line->pos != -1 && neighborSet[k].line->key != updateKey){
            neighborSet[k].line->calcDiff(point, Q, father);
            heap->update(neighborSet[k].line->pos);
            neighborSet[k].line->key = updateKey;
        }
    }
}

bool ComplexObj::intersect(const Ray &ray, Vec &P, Vec &N, Material &material)
{

    //        int isCrash = 0;
    //        int id = -1;
    //        Vec nP , nN; //碰撞点和反射面法向量，nP和nN只是临时变量
    //        for(int i = 0; i < faceSize; i++) { //枚举每一个物体
    //            int check = 0;
    //            check = triangle[i].intersect( ray, nP , nN ); //计算碰撞点和反射面法向量，返回碰撞方式
    //            if ( check != 0 && ( id == -1 || ( nP - ray.ori ).length() < ( P - ray.ori ).length() ) ) {
    //                isCrash = check; //找一个最近的碰撞点并记录信息
    //                id = i;
    //                P = nP;
    //                N = nN;
    //            }
    //        }
    //        return isCrash;
    return root->intersect(ray, P, N, material);
}

void ComplexObj::updateQ(Triangle & tt)
{
    Matrix m;
    if (tt.N.length() > zero) {
        double a[4] = {tt.N.x, tt.N.y, tt.N.z, tt.D };
        for (int i = 0 ; i < 4; i++){
            for (int j = 0 ; j < 4; j++){
                m.matrix[i][j] = a[i] * a[j];
            }
        }
    }

    int p1 = tt.d1;
    int p2 = tt.d2;
    int p3 = tt.d3;
    Q[p1] += m, Q[p1] -= tt.mm;
    if (p2 != p1)
        Q[p2] += m, Q[p2] -= tt.mm;
    if (p3 != p1 && p3 != p2)
        Q[p3] += m, Q[p3] -= tt.mm;

    tt.mm = m;
}

int ComplexObj::merge(Edge* cur)
{
    //===============合并点================
    int faceDelSize = 0;
    int x = getFather(cur->x);
    int y = getFather(cur->y);
    father[y] = x;
    point[x] = cur->recom;
    point[y] = cur->recom;
    updateKey++;

    pointBuff.clear();
    for (int k = start[x]; k != 0 ; k = neiFace[k].next){
        Vec n1 = neiFace[k].face->N;
        neiFace[k].face->update(point, father, updateKey);
        Vec n2 = neiFace[k].face->N;
        if (n1.length() > zero && n2.length() < zero) faceDelSize++;
        updateQ(*neiFace[k].face);
        pointBuff.push_back(neiFace[k].face->d1);
        pointBuff.push_back(neiFace[k].face->d2);
        pointBuff.push_back(neiFace[k].face->d3);
        //        updateP(getFather(neiFace[k].face->d1));
        //        updateP(getFather(neiFace[k].face->d2));
        //        updateP(getFather(neiFace[k].face->d3));
    }

    int next;
    for (int k = start[y]; k != 0 ; k = next){
        next = neiFace[k].next;
        if (neiFace[k].face->key != updateKey){
            neiFace[k].next = start[x];
            start[x] = k;
            Q[x] += neiFace[k].face->mm;

            neiFace[k].face->update(point, father, updateKey);
            updateQ(*neiFace[k].face);
            pointBuff.push_back(neiFace[k].face->d1);
            pointBuff.push_back(neiFace[k].face->d2);
            pointBuff.push_back(neiFace[k].face->d3);
            //            updateP(getFather(neiFace[k].face->d1));
            //            updateP(getFather(neiFace[k].face->d2));
            //            updateP(getFather(neiFace[k].face->d3));
        }else{
            pointKey[neiFace[k].face->d1] = updateKey;
            pointKey[neiFace[k].face->d2] = updateKey;
            pointKey[neiFace[k].face->d3] = updateKey;
        }
    }
    for (int k = neighborHead[y]; k != 0 ; k = next){
        next = neighborSet[k].next;
        if (pointKey[getFather(neighborSet[k].line->x)] != updateKey ||
                pointKey[getFather(neighborSet[k].line->y)] != updateKey){
            neighborSet[k].next = neighborHead[x];
            neighborHead[x] = k;
        }else {
            if (neighborSet[k].line->pos != -1){
                heap->del(neighborSet[k].line->pos);
            }
        }
    }
    updateP(x, updateKey);
    int buffSize = pointBuff.size();
    for(int i = 0; i < buffSize; i++){
        if (pointKey[pointBuff[i]] != updateKey){
            updateP(pointBuff[i], updateKey);
            pointKey[pointBuff[i]] = updateKey;
        }
    }
    return faceDelSize;
}






void ComplexObj::simplified(double rate)
{
    //============初始化======================
    usedSize = 0;
    lineSize = 0;
    listSize = 0;
    updateKey = 0;
    neighborHead = new int[pointSize + 5];
    start = new int[pointSize + 5];
    father = new int[pointSize + 5];
    pointKey = new int[pointSize + 5];

    for(int i = 0; i <= pointSize; i++){
        neighborHead[i] = 0;
        start[i] = 0;
        father[i] = i;
        pointKey[i] = 0;
    }


    Q.resize(pointSize + 5);
    neighborSet = new List[faceSize * 3 + 5];
    neiFace = new ListT[faceSize * 3 + 5];
    line = new Edge[faceSize * 3 / 2]; // ?
    heap = new Heap(faceSize * 3 / 2);
    usedSize = 0;
    listSize = 0;

    for(int i = 0; i < faceSize; i++){
        Triangle tt = triangle[i];
        updateQ(triangle[i]);
        inn(tt.d1, &triangle[i]);
        inn(tt.d2, &triangle[i]);
        inn(tt.d3, &triangle[i]);
        inse(tt.d1, tt.d2);
        inse(tt.d2 ,tt.d3);
        inse(tt.d3, tt.d1);
    }

    //==================生成堆=====================
    for (int i = 0; i < lineSize; i++){
        line[i].calcDiff(point, Q, father);
        heap->insert(&line[i]);
    }

    //=============开始工作，每次坍缩一条边===========
    int left = faceSize;
    while (left > rate * faceSize){
        Edge* cur = heap->pop();
        left -= merge(cur);
    };

    //=============删除旧的面=======================
    int newFaceSize = 0;
    for (int i = 0; i < faceSize; i++)
    {
        if( (triangle[i]).N.length() > zero ){
            triangle[newFaceSize] = triangle[i];
            newFaceSize ++;
            //fprintf(fp, "f %d %d %d\n", getFather(triangle[i].d1), getFather(triangle[i].d2), getFather(triangle[i].d3));
        }
    }
    cout << "newFaceSize : " << newFaceSize << endl;

    faceSize = newFaceSize;
}

void ComplexObj::output(string file)
{
    FILE* fp = fopen(file.c_str(), "w");
    fprintf(fp, "# faceSize %d\n", faceSize);
    for (int i = 1; i <= pointSize; i++){
        fprintf(fp, "v %.5lf %.5lf %.5lf\n", point[i].x, point[i].y, point[i].z);
        //fprintf(fp, "v %.5lf %.5lf %.5lf\n", 1.0, 1.0, 1.0);
    }


    for (int i = 0; i < faceSize; i++)
    {
        if( (triangle[i]).N.length() > zero ){
            fprintf(fp, "f %d %d %d\n", triangle[i].d1, triangle[i].d2, triangle[i].d3);
        }
    }
    fclose(fp);
}



bool Node::intersect(const Ray &ray, Vec &P, Vec &N, Material &material)
{
    if (isLeaf){
        int isCrash = 0;
        int id = -1;
        Vec nP , nN;
        Material nMaterial;
        for(int i = 0; i < faceSize; i++) {
            int check = 0;
            //            cout << "tri {";
            //            cout << face[i]->p1 << endl;
            //            cout << face[i]->p2 << endl;
            //            cout << face[i]->p3 << endl;
            //            cout << "}" << endl;
            check = face[i]->intersect( ray, nP , nN, nMaterial);
            if ( check != 0 && ( id == -1 || ( nP - ray.ori ).length() < ( P - ray.ori ).length() ) ) {
                isCrash = check;
                id = i;
                P = nP;
                N = nN;
                material = nMaterial;
            }
        }
        return isCrash;
    }
    Ray r = ray;
    double leftDis = leftSon->cube.intersect(r);
    double rightDis = rightSon->cube.intersect(r);
    if (leftDis < EPS){
        if (rightDis < EPS){
            return 0;
        }else {
            return rightSon->intersect(ray, P, N, material);
        }
    }else{
        if (rightDis < EPS){
            return leftSon->intersect(ray, P, N, material);
        }else {
            if (fabs(leftDis - rightDis) < EPS){
                Vec P1, N1, P2, N2;
                Material material1, material2;
                bool c1 = leftSon->intersect(ray, P1, N1, material1);
                bool c2 = rightSon->intersect(ray, P2, N2, material2);
                if (c1 && (!c2 || (P1 - ray.ori).length() < (P2 - ray.ori).length()) ){
                    P = P1;
                    N = N1;
                    material = material1;
                    return c1;
                }else{
                    P = P2;
                    N = N2;
                    material = material2;
                    return c2;
                }
            }else{
                if (leftDis < rightDis){
                    bool crash = leftSon->intersect(ray, P, N, material);
                    if (!crash){
                        return rightSon->intersect(ray, P, N, material);
                    }
                    return crash;
                }else {
                    bool crash = rightSon->intersect(ray, P, N, material);
                    if (!crash){
                        return leftSon->intersect(ray, P, N, material);

                    }
                    return crash;
                }
            }
        }
    }

}

void Node::makeKDTree(int type)
{
    if (PointSize <= 10){
        isLeaf = 1;
        return;
    }

    int faceSize = face.size();
    int pointSize = point.size();

    Compare::type = type;
    sort(point.begin(), point.end(), Compare());

    double mid = (*point[pointSize / 2])[type];

    leftSon = new Node();
    leftSon->cube = this->cube;
    leftSon->cube.large[type] = mid;

    rightSon = new Node();
    rightSon->cube = this->cube;
    rightSon->cube.small[type] = mid;

    for (int i = 0; i < faceSize; i++){
        if (face[i]->p1[type] < mid + EPS || face[i]->p2[type] < mid + EPS || face[i]->p3[type] < mid + EPS){
            leftSon->face.push_back(face[i]);
            leftSon->faceSize++;
        }

        if (face[i]->p1[type] > mid - EPS || face[i]->p2[type] > mid - EPS || face[i]->p3[type] > mid - EPS){
            rightSon->face.push_back(face[i]);
            rightSon->faceSize++;
        }
    }

    for (int i = 0; i < pointSize / 2; i++){
        leftSon->point.push_back(point[i]);
        leftSon->PointSize++;
    }

    for (int i = pointSize / 2; i < pointSize; i++){
        rightSon->point.push_back(point[i]);
        rightSon->PointSize++;
    }

    leftSon->makeKDTree((type + 1) % 3);
    rightSon->makeKDTree((type + 1) % 3);
}
